1. Field of the Invention
The present invention relates to an improved carry look-ahead technique, used, for example, in an adder.
2. Description of the Prior Art
Carry look-ahead (CLA) is the predominant technique for high performance adders used in microprocessors, digital signal processors, and other integrated circuits. An overview of carry look-ahead adder theory is given in Digital Computer Arithmetic, by J. J. F. Cavanagh, p. 107-117, McGraw-Hill (1984). To save computation time, a CLA computes the carry inputs to all of the bit adder stages in parallel (i.e., simultaneously). For this purpose, two auxiliary signals, the "generate" and the "propagate" are produced. The generate (G) signal is a logic "1" when a carry is generated at a given state (and "0" otherwise); and the propagate (P) signal is a logic "1" when a given stage will pass (i.e., propagate) the incoming carry to the next higher stage (and "0" if it will not). The G and P signals are then combined in logic circuitry to produce the bit carries. For example, when adding 64 bit numbers, it is theoretically possible that 64 G signals and 64 P signals may be combined to produce 64 bit carries in the same logic level. However, the fan-in limitations of most integrated circuit technologies prevents the carry generating circuitry from accepting all 64 G and 64 P signals simultaneously. In most technologies, the optimal fan-in limitation of the circuit prevents more than 4 pairs of terms from being combined in a given circuit. Therefore, the G and P signals are combined in groups of 4 (or less). The outputs of these groups are then combined at higher levels to achieve the final bit carries.
This division of the total number of stages into groups is referred to as "partitioning". In order to achieve maximum circuit speed, it is necessary to reduce the number of logic levels used to generate the bit carry signals. Hence, it is desirable that each group receives the maximum possible number of inputs, without exceeding the fan-in limit. In that manner, the delay time, being proportional to the number of logic levels required to produce the bit carries, is minimized. For example, when adding two 64 bit numbers, the typical partitioning scheme provides for four "sections" with four "groups" per section, and four bits per group. This partitioning scheme is then referred to as a "1 bit/4 bit/16 bit" partition. In the first level, G and P terms are produced for each bit position; in the second level, 4 G and 4 P terms are combined to produce 4 group generate (GG) and 4 group propagate (GP) terms; in the third level, 4 GG and 4 GP terms are combined to produce 3 section carry (SC) terms and the carry-out term. The carry-in term and the 3 SC terms are combined with the GG and GP terms to produce the group carry (GC) terms. The GC terms are combined with the G and P terms to produce the bit carries. It can thus be seen that for carry look-ahead adders whose data path width is an integral power of 4 (e.g., 64=4.sup.3), the prior art partitioning scheme combines 4 bits for producing terms at each level.
However, for adders whose data path width is not a power of 4, (for example, 32 bit wide data paths), the prior partitioning scheme has been retained. That is, microprocessors and other types of ICs that utilize 32 bit data paths have used the above-described partitioning scheme, which was developed originally for computer main-frame technologies using 16 or 64 bit data paths.